package com.sqi.algorithm.game;

import java.util.ArrayList;
import java.util.List;


//static int[][] sudoKu = {
//        {0, 0, 0, 0, 0, 0, 0, 0, 0},
//        {0, 0, 0, 0, 0, 0, 0, 0, 0},
//        {0, 0, 0, 0, 0, 0, 0, 0, 0},
//        {0, 0, 0, 0, 0, 0, 0, 0, 0},
//        {0, 0, 0, 0, 0, 0, 0, 0, 0},
//        {0, 0, 0, 0, 0, 0, 0, 0, 0},
//        {0, 0, 0, 0, 0, 0, 0, 0, 0},
//        {0, 0, 0, 0, 0, 0, 0, 0, 0},
//        {0, 0, 0, 0, 0, 0, 0, 0, 0}
//        };

/**
 * @Author songjinlong
 * @Date 2021/7/16
 * @Version V1.0.0
 **/
public class Sudoku {
    static List<Point> points = new ArrayList<>();
    static int[][] sudoKu = {
            {8, 0, 0, 0, 0, 0, 0, 0, 0},
            {0, 0, 3, 6, 0, 0, 0, 0, 0},
            {0, 7, 0, 0, 9, 0, 2, 0, 0},
            {0, 5, 0, 0, 0, 7, 0, 0, 0},
            {0, 0, 0, 0, 4, 5, 7, 0, 0},
            {0, 0, 0, 1, 0, 0, 0, 3, 0},
            {0, 0, 1, 0, 0, 0, 0, 6, 8},
            {0, 0, 8, 5, 0, 0, 0, 1, 0},
            {0, 9, 0, 0, 0, 0, 4, 0, 0}
    };

    static int[] times = new int[9];
    static int[] sortIndex = new int[9]; //{2, 3, 4, 6, 9, 1, 5, 7, 8};

    public static void main(String[] args) {
        long st = System.currentTimeMillis();
        boolean[] temp = new boolean[325];
        for (int x = 1; x < 10; x++) {
            for (int y = 1; y < 10; y++) {
                int v = sudoKu[x - 1][y - 1];
                if (v > 0) {
                    times[v - 1]++;
                    temp[index(x, y)] = true;
                    temp[rowIndex(x, v)] = true;
                    temp[colIndex(y, v)] = true;
                    temp[palaceIndex(x, y, v)] = true;
                }
            }
        }
        int tMax = 1;
        int j = 0;
        while (tMax > 0) {
            int tMM = 0;
            for (int i = 0; i < times.length; i++) {
                if (times[i] == 1) {
                    sortIndex[j++] = i + 1;
                }
                times[i]--;
                if (times[i] > tMM) {
                    tMM = times[i];
                }
            }
            tMax = tMM;
        }
        SudokuSearch ss = new SudokuSearch();
        points.add(new Point(0, 0, 0));
        int lineNum = 1;
        for (int x = 1; x < 10; x++) {
            for (int y = 1; y < 10; y++) {
                if (sudoKu[x - 1][y - 1] == 0) {
                    for (int v = 1; v < 10; v++) {
                        int x1 = index(x, y);
                        int x2 = rowIndex(x, v);
                        int x3 = colIndex(y, v);
                        int x4 = palaceIndex(x, y, v);
                        if (!temp[x1] && !temp[x2] && !temp[x3] && !temp[x4]) {
                            ss.addLine(x1, x2, x3, x4, lineNum, v);
                            points.add(lineNum, new Point(x, y, v));
                            lineNum++;
                        }
                    }
                }
            }
        }
        ss.getLineNumResult();
        long et = System.currentTimeMillis();
        System.out.println("用时：：" + (et - st) + "ms");
        printSudoku();
    }

    private static int index(int x, int y) {
        return (x - 1) * 9 + y;
    }

    private static int rowIndex(int x, int value) {
        return 81 + (x - 1) * 9 + value;
    }

    private static int colIndex(int y, int value) {
        return 162 + (y - 1) * 9 + value;
    }

    private static int palaceIndex(int x, int y, int value) {
        return 243 + (palaceNum(x, y) - 1) * 9 + value;
    }

    private static int palaceNum(int x, int y) {
        return (x - 1) / 3 * 3 + (y - 1) / 3 + 1;
    }

    private static void printSudoku() {
        for (int[] ints : sudoKu) {
            for (int anInt : ints) {
                System.out.print(anInt + " ");
            }
            System.out.println();
        }
    }

    private static class SudokuSearch {
        private final Node[] columnMark = new Node[325];
        private final Node head = new Node(0, 10);

        public SudokuSearch() {
            head.colCount = Integer.MAX_VALUE;
            for (int i = 0; i < columnMark.length; i++) {
                columnMark[i] = new Node(0, 10);
                columnMark[i].col = columnMark[i];
            }

        }

        public void addLine(int index1, int index2, int index3, int index4, int lineNum, int v) {
            Node node1 = new Node(lineNum, v);
            Node node2 = new Node(lineNum, v);
            Node node3 = new Node(lineNum, v);
            Node node4 = new Node(lineNum, v);

            node1.right = node2;
            node1.left = node4;
            node1.col = columnMark[index1];
            node2.right = node3;
            node2.left = node1;
            node2.col = columnMark[index2];

            node3.right = node4;
            node3.left = node2;
            node3.col = columnMark[index3];

            node4.right = node1;
            node4.left = node3;
            node4.col = columnMark[index4];

            addCol(node1, index1);
            addCol(node2, index2);
            addCol(node3, index3);
            addCol(node4, index4);
        }

        private void addCol(Node node, int index) {
            Node temp = columnMark[index].up;
            if (temp == null) {
                columnMark[index].down = node;
                columnMark[index].up = node;
                node.down = columnMark[index];
                node.up = columnMark[index];
            } else {
                temp.down = node;
                columnMark[index].up = node;
                node.down = columnMark[index];
                node.up = temp;
            }
            columnMark[index].colCount++;
            if (node.nodeValue < columnMark[index].colMinValue && index < 82) {
                columnMark[index].colMinValue = node.nodeValue;
            }
        }

        public void getLineNumResult() {
            linkList();
            if (search()) {
                //                printSudoku();
            } else {
                System.out.println("无解");
            }

        }

        private void linkList() {
            Node temp = head;
            for (Node node : columnMark) {
                if (node.colCount > 0) {
                    temp.right = node;
                    node.left = temp;

                    temp = node;
                }
            }
            head.left = temp;
            temp.right = head;
            sort();
        }

        private void sort() {
            for (int i = sortIndex.length - 1; i >= 0; i--) {
                int v = sortIndex[i];
                Node temp = head.right;
                while (temp.colMinValue < 10) {
                    Node tR = temp.right;
                    if (temp.colMinValue == v) {
                        temp.right.left = temp.left;
                        temp.left.right = temp.right;

                        temp.right = head.right;
                        temp.left = head;
                        head.right = temp;
                        temp.right.left = temp;
                    }
                    temp = tR;
                }
            }
        }

        private void deleteCurrNode(Node currNode) {
            Node colNode = currNode.col;
            colNode.left.right = colNode.right;
            colNode.right.left = colNode.left;
            Node cNode = colNode.down;
            while (cNode != colNode) {
                Node rNode = cNode.right;
                while (rNode != cNode) {
                    rNode.down.up = rNode.up;
                    rNode.up.down = rNode.down;
                    rNode.col.colCount--;
                    rNode = rNode.right;
                }
                cNode = cNode.down;
            }
        }

        private void addCurrNode(Node currNode) {
            Node colNode = currNode.col;
            Node cNode = colNode.down;
            while (cNode != colNode) {
                Node leftNode = cNode.left;
                while (leftNode != cNode) {
                    leftNode.down.up = leftNode;
                    leftNode.up.down = leftNode;
                    leftNode.col.colCount++;
                    leftNode = leftNode.left;
                }
                cNode = cNode.down;
            }
            colNode.left.right = colNode;
            colNode.right.left = colNode;
        }

        private boolean search() {
            Node cRoot = head.right;
            if (cRoot == head) {
                return true;
            }
            Node currNode;
            for (Node currRow = cRoot.down; currRow != cRoot; currRow = currRow.down) {
                Point point = points.get(currRow.lineNum);
                sudoKu[point.x - 1][point.y - 1] = point.v;
                currNode = currRow;
                do {
                    deleteCurrNode(currNode);
                    currNode = currNode.right;
                } while (currNode != currRow);
                if (search()) {
                    return true;
                }
                do {
                    addCurrNode(currNode);
                    currNode = currNode.left;
                } while (currNode != currRow);
            }
            return false;
        }

        private static class Node {
            private Node left, right, up, down, col;
            private final int lineNum;
            private int colCount = 0;
            private int colMinValue = 10;
            private final int nodeValue;

            public Node(int lineNum, int v) {
                this.lineNum = lineNum;
                this.nodeValue = v;
            }
        }
    }

    private static class Point {
        int x;
        int y;
        int v;

        public Point(int x, int y, int v) {
            this.x = x;
            this.y = y;
            this.v = v;
        }
    }
}
